#include <stack>
#include <queue>
#include <set>
#include "Tree.h"

using namespace std;

TreeNode* CreateTree()
{
	TreeNode* node1 = new TreeNode(10);
	TreeNode* node21 = new TreeNode(5);
	TreeNode* node22 = new TreeNode(15);
	TreeNode* node31 = new TreeNode(8);
	TreeNode* node32 = new TreeNode(13);
	TreeNode* node33 = new TreeNode(16);
	TreeNode* node41 = new TreeNode(6);
	TreeNode* node42 = new TreeNode(9);
	TreeNode* node43 = new TreeNode(14);

	node1->left = node21;
	node1->right = node22;

	node21->right = node31;
	node22->left = node32;
	node22->right = node33;

	node31->left = node41;
	node31->right = node42;
	node32->right = node43;

	return node1;
}

void PreOrderVisitTreeR(TreeNode* node)
{
	if (NULL == node)
	{
		return;
	}

	printf("%d,", node->val);
	PreOrderVisitTreeR(node->left);
	PreOrderVisitTreeR(node->right);
}

void MidOrderVisitTreeR(TreeNode* node)
{
	if (NULL == node)
	{
		return;
	}

	MidOrderVisitTreeR(node->left);
	printf("%d,", node->val);
	MidOrderVisitTreeR(node->right);
}

void PostOrderVisitTreeR(TreeNode* node)
{
	if (NULL == node)
	{
		return;
	}

	PostOrderVisitTreeR(node->left);
	PostOrderVisitTreeR(node->right);
	printf("%d,", node->val);
}

void PreOrderVisitTree(TreeNode* node)
{
	if (NULL == node)
	{
		return;
	}

	queue<TreeNode*> nodeQueue;
	TreeNode* tmp = node;
	while(tmp)
	{
		nodeQueue.push(tmp);
		if (tmp->left)
		{
			nodeQueue.push(tmp->left);
		}
		if (tmp->right)
		{
			nodeQueue.push(tmp->right);
		}
	}
}

void MidOrderVisitTree(TreeNode* node)
{

}

void PostOrderVisitTree(TreeNode* node)
{

}

void LayerVisitTree(TreeNode* node)
{
	int level = 1;
	queue<TreeNode*> nodeQueue;
	nodeQueue.push(node);
	while(!nodeQueue.empty())
	{
		printf("level %d ", level++);
		
		int levelNum = nodeQueue.size();
		for (int i = 0; i < levelNum; ++i)
		{
			TreeNode* tmp = nodeQueue.front();
			nodeQueue.pop();
			if (NULL == tmp)
			{
				continue;
			}
			printf("%d,", tmp->val);
			if (tmp->left)
			{
				nodeQueue.push(tmp->left);
			}
			if (tmp->right)
			{
				nodeQueue.push(tmp->right);
			}
		}
		printf("\n");
	}
}

void BreadthVisitTree(TreeNode* node)
{
	queue<TreeNode*> nodeQueue;
	nodeQueue.push(node);
	while(!nodeQueue.empty())
	{
		TreeNode* tmp = nodeQueue.front();
		nodeQueue.pop();
		if (NULL == tmp)
		{
			continue;
		}
		printf("%d,", tmp->val);
		if (tmp->left)
		{
			nodeQueue.push(tmp->left);
		}
		if (tmp->right)
		{
			nodeQueue.push(tmp->right);
		}
	}
}

void DepthVisitTreeR(TreeNode* node)
{
	if (NULL == node)
	{
		return;
	}
	printf("%d,", node->val);
	if (node->left)
	{
		DepthVisitTreeR(node->left);
	}
	if (node->right)
	{
		DepthVisitTreeR(node->right);
	}
}

void DepthVisitTree(TreeNode* node)
{
	if (NULL == node)
	{
		return;
	}
	set<TreeNode*> nodeSet;
	stack<TreeNode*> nodeStack;
	nodeStack.push(node);
	while(!nodeStack.empty())
	{
		TreeNode* tmp = nodeStack.top();
		if (nodeSet.find(tmp) == nodeSet.end())
		{
			printf("%d,", tmp->val);
			nodeSet.insert(tmp);
		}
		if (tmp->left && nodeSet.find(tmp->left) == nodeSet.end())
		{
			nodeStack.push(tmp->left);
		}
		else if (tmp->right && nodeSet.find(tmp->right) == nodeSet.end())
		{
			nodeStack.push(tmp->right);
		}
		else
		{
			nodeStack.pop();
		}
	}
}

void MaxMinDepth(TreeNode* node, int& max, int& min)
{
	int level = 1;
	queue<TreeNode*> nodeQueue;
	nodeQueue.push(node);
	while(!nodeQueue.empty())
	{
		int levelNum = nodeQueue.size();
		for (int i = 0; i < levelNum; ++i)
		{
			TreeNode* tmp = nodeQueue.front();
			nodeQueue.pop();
			if (NULL == tmp)
			{
				continue;
			}
			if (tmp->left)
			{
				nodeQueue.push(tmp->left);
			}
			if (tmp->right)
			{
				nodeQueue.push(tmp->right);
			}
			if (tmp->left == NULL && tmp->right == NULL && min == 0)
			{
				min = level;
			}
		}
		if (level > max)
		{
			max = level;
		}
		level++;
	}
}

bool ValidateBST1(TreeNode* node, int preVal)
{
	if (NULL == node)
	{
		return true;
	}

	if (!ValidateBST1(node->left,preVal))
	{
		return false;
	}
	
	if (preVal > node->val)
	{
		return false;
	}

	return  ValidateBST1(node->right, node->val);
}

bool ValidateBST2(TreeNode* node, int min, int max)
{
	if (NULL == node)
	{
		return true;
	}

	if (node->val <= min || node->val >= max)
	{
		return false;
	}

	return ValidateBST2(node->left, min, node->val) 
		&& ValidateBST2(node->right, node->val, max);
}

bool FindNodePath(TreeNode* node, int target, NodePath& rPath)
{
	if (NULL == node)
	{
		return false;
	}

	rPath.push_back(node);
	if (node->val == target)
	{
		return true;
	}
	if (FindNodePath(node->left, target, rPath))
	{
		return true;
	}
	else if (FindNodePath(node->right, target, rPath))
	{
		return true;
	}
	else
	{
		rPath.pop_back();
		return false;
	}
}

TreeNode* LowestCommonAncestor1(TreeNode* node, int a, int b)
{
	TreeNode* result = NULL;
	NodePath pathA, pathB;
	FindNodePath(node, a, pathA);
	FindNodePath(node, b, pathB);
	unsigned i = 0;
	while(i < pathA.size() && i < pathB.size())
	{
		if (pathA[i] == pathB[i])
		{
			result = pathA[i];
		}
		else
		{
			break;
		}
		i++;
	}

	return result;
}

TreeNode* LowestCommonAncestor2(TreeNode* node, int a, int b)
{
	if (NULL == node)
	{
		return NULL;
	}

	if (node->val == a || node->val == b)
	{
		return node;
	}

	TreeNode* left = LowestCommonAncestor2(node->left, a, b);
	TreeNode* right = LowestCommonAncestor2(node->right, a, b);
	if (NULL == left)
	{
		return right;
	}
	else if (NULL == right)
	{
		return left;
	}
	else
	{
		return node;
	}
}

TreeNode* LowestCommonAncestor3(TreeNode* node, int a, int b)
{
	if (NULL == node)
	{
		return NULL;
	}
	if (node->val > a && node->val > b)
	{
		LowestCommonAncestor3(node->left, a, b);
	}
	else if (node->val < a && node->val < b)
	{
		LowestCommonAncestor3(node->right, a, b);
	}
	else
	{
		return node;
	}
}
